package org.hhchat.leetcode.dp;

/**
 * Created this one by HMH on 2017/6/13.
 */
public class code63 {
    public static class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int dp[][] = new int[m + 1][n + 1];
            dp[1][1]=obstacleGrid[0][0]==1?0:1;
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++) {
                    if (obstacleGrid[i - 1][ j - 1]!= 1 && !(i==1 && j==1)) {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
            return dp[m][n];
        }

    }
    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.uniquePathsWithObstacles(new int[][]{
//                {0,0,0,0},
//                {0,1,0,0},
//                {0,0,0,0},
//                {0,0,1,0},
//                {0,0,0,0}
//                {0,0},
//                {1,1},
//                {0,0}
                {0}
        }));
    }
}

//leetcode解法

//不需要初始化1,1，可以初始化0,1即可保证1,1是正确的
//public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//    int width = obstacleGrid[0].length;
//    int[] dp = new int[width];
//    dp[0] = 1;
//    for (int[] row : obstacleGrid) {
//        for (int j = 0; j < width; j++) {
//            if (row[j] == 1)
//                dp[j] = 0;
//            else if (j > 0)
//                dp[j] += dp[j - 1];
//        }
//    }
//    return dp[width - 1];
//}

//    另外有一个o(n)空间的解法
//    int width = obstacleGrid[0].length;
//    int[] dp = new int[width];
//    dp[0] = 1;
//    for (int[] row : obstacleGrid) {
//        for (int j = 0; j < width; j++) {
//            if (row[j] == 1)
//                dp[j] = 0;
//            else if (j > 0)
//                dp[j] += dp[j - 1];
//        }
//    }
//    return dp[width - 1];